package leetcode.hot100;

import java.util.Arrays;

public class Solution322 {

    public static void main(String[] args) {

        int[] coins = {2};
        System.out.println(new Solution322().coinChange(coins,3));

    }

    public int coinChange(int[] coins, int amount) {
        //动态规划：复杂度coinsLen*amount，顶多10^5
        //dp[i]表示凑够面额i需要的最少硬币数，如果凑不成，置为-1
        //dp[i]=min{dp[dp[i]-coins[j]]+1}, 0<=j<coins.len&&coins[j]<=i&&dp[dp[i]-coins[j]]!=-1
        if(amount==0) return 0;
        int[] dp = new int[amount+1];
        int coinNum = coins.length;
        Arrays.fill(dp,1,amount+1,Integer.MAX_VALUE);
        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < coinNum; j++) {
                if(coins[j]>i) break;
                int other = dp[i-coins[j]];
                if(other!=Integer.MAX_VALUE) dp[i] = Math.min(dp[i],other+1);
            }
        }
        return dp[amount]==Integer.MAX_VALUE?-1:dp[amount];
    }
}
